package com.example.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by Quincy on 2018/9/12.
 * 二叉树的遍历
 */
public class BinaryTreeTraversal {
    public class TreeNode{
        int val;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode (int val){
            this.val = val;
        }
    }

    /**
     * 递归
     * */
    //后序遍历，左=》右=》根
    public void postorder_Traversal(TreeNode root)
    {
        if(root==null)return;
        postorder_Traversal(root.left);
        postorder_Traversal(root.right);

        //访问节点的逻辑代码块
        System.out.print(root.val+" ");
    }
    //前序遍历，根=》左=》右
    public void preorder_Traversal(TreeNode root)
    {
        if(root==null)return;

        //访问节点的逻辑代码块
        System.out.print(root.val+" ");

        preorder_Traversal(root.left);
        preorder_Traversal(root.right);
    }
    //中序遍历，左=》根=》右
    public void inorder_Traversal(TreeNode root)
    {
        if(root==null)return;
        inorder_Traversal(root.left);

        //访问节点的逻辑代码块
        System.out.print(root.val+" ");

        inorder_Traversal(root.right);
    }

    /**
     *  非递归
     * */
    //前序非递归遍历，根=》左=》右
    public void preorder(TreeNode root)
    {
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty())
        {
            //当前节点不为空，则入栈，确保最后遍历到的节点没有左子节点
            //因为是前序遍历，所以再遍历到每个节点的时候，都可以先访问，再寻找其左右子节点。
            while(root!=null)
            {
                System.out.print(root.val+" ");
                stack.push(root);
                root=root.left;
            }
            if(!stack.empty())
            {
                //把这两步看成是一步，找到右节点，并把已处理的中节点从stack当中去除
                root=stack.pop();
                root=root.right;
            }
        }
    }

    //中序遍历非递归
    public void Inorder(TreeNode root)
    {
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty())
        {
            //当前节点不为空，则入栈，确保最后遍历到的节点没有左子节点
            while(root!=null)
            {
                stack.push(root);
                root=root.left;
            }
            //通过当前节点，跳到当前节点的右节点，因为是中序遍历，所以当前节点没有左节点的时候，就可以访问当前节点
            if(!stack.empty())
            {
                root=stack.pop();
                System.out.print(root.val+" ");
                root=root.right;
            }
        }
    }

    //后序遍历非递归
    public void Postorder(TreeNode root)
    {
        Stack<TreeNode> s =new Stack<>();
        Stack<Integer> s2 =new Stack<>();
        Integer i=new Integer(1);
        while(root!=null||!s.isEmpty())
        {
            //只要当前节点非空，就入栈
            while(root!=null)
            {
                s.push(root);
                s2.push(new Integer(0));
                root=root.left;
            }
            //s2当中如果存1，则意味着当前s1对应的节点的左右子节点都已经遍历过了。
            while(!s.empty()&&s2.peek().equals(i))
            {
                s2.pop();
                System.out.print(s.pop().val+" ");
            }
            if(!s.isEmpty())
            {
                s2.pop();
                s2.push(new Integer(1));
                root=s.peek();
                root=root.right;
            }

        }
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.push(root);
        while ( !deque.isEmpty()){
            TreeNode temp = deque.poll();
            System.out.print(temp.val);
            if (temp.left != null){
                deque.push(temp.left);
            }
            if (temp.right != null){
                deque.push(temp.right);
            }
        }
    }

    //不使用队列
    public static void levelTraversal(TreeNode root)
    {
        ArrayList<TreeNode> list = new ArrayList<>();
        list.add(root);
        while(!list.isEmpty())
        {
            ArrayList<TreeNode> temp = new ArrayList<>();
            for (TreeNode node : list)
            {
                System.out.print(node.val);
                if(node.left != null)
                {
                    temp.add(node.left);
                }
                if(node.right != null)
                {
                    temp.add(node.right);
                }
            }
            list = temp;
        }
    }
}
